package com.example.validatestudy.demos.algorithm.backtracking;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * 回溯算法思想
 *
 */
public class Combination {

    /**
     * 组合问题
     * 力扣地址  https://leetcode.cn/problems/combinations/description/
     * @param args
     */
    public static void main(String[] args) {

        List<List<Integer>> r =   new Combination().combine(4,2);
        System.out.println(r.toString());
    }

    public static List<List<Integer>> result = new ArrayList();//结果集合
    public static LinkedList<Integer> path = new LinkedList();//单个结果

    public static List<List<Integer>> combine(int n, int k) {
        back(n,k,1);
        return result;
    }

    public static void back(int n,int k,int start){
        if(path.size()==k){
            result.add(new ArrayList<>(path));
            return;
        }
        for(int i=start;i<=n;i++){
            path.add(i);
            back(n,k,i+1);
            path.removeLast();
        }
    }


}
